1772C - Different Differences - CodeForces Solution


constructive algorithms greedy math *1000

Please click on ads to support us..

Python Code:

import sys
from os import path


def input():
    return sys.stdin.readline().strip()


def solve(k, n):
    def make_d(f, k):
        return [(i + 2 if i < f - 1 else 1) for i in range(k)]
    ans = 1
    for f in range(1, k):
        d = make_d(f, k - 1)
        if sum(d) <= n - 1:
            dd = d
    r = [1]
    for x in dd:
        r.append(r[-1] + x)
    print(*r)


def main():
    testcases = int(input())      for _ in range(testcases):
        k, n = list(map(int, input().split()))
        solve(k, n)


if __name__ == "__main__":

    if path.exists('Tests'):
        sys.stdin = open("Tests/input_1.txt", "r")
        sys.stdout = open("Tests/output_1a.txt", "w")

    main()

C++ Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

ll lcm(ll a, ll b) { return a * b / __gcd(a, b); }
ll expo(ll a, ll b, ll mod) {
  ll res = 1;
  while (b > 0) {
    if (b & 1)
      res = (res * a) % mod;
    a = (a * a) % mod;
    b = b >> 1;
  }
  return res;
}
void extendgcd(ll a, ll b, ll *arr) {  //ax+by=gcd(a,b);
  if (b == 0) {
    arr[0] = 1;
    arr[1] = 0;
    arr[2] = a;
    return;
  }
  extendgcd(b, a % b, arr);
  ll x1 = arr[1];
  arr[1] = arr[0] - (a / b) * arr[1];
  arr[0] = x1;
  return;
}
ll mminv(ll a, ll m) {
  ll arr[3];
  extendgcd(a, m, arr);
  if (arr[2] != 1) {
    return -1;
  }
  return (arr[0] % m + m) % m;
} // if m is non prime
ll mminvprime(ll a, ll m) { // if a is prime
  return expo(a, m - 2, m);
}
vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll mod_add(ll a, ll b, ll m) {
  a = a % m;
  b = b % m;
  return (((a + b) % m + m) % m);
}
ll mod_sub(ll a, ll b, ll m) {
  a = a % m;
  b = b % m;
  return (((a - b) % m + m) % m);
}
ll mod_mul(ll a, ll b, ll m) {
  a = a % m;
  b = b % m;
  return (((a * b) % m + m) % m);
}
ll mod_div(ll a, ll b, ll m) {
  a = a % m;
  b = b % m;
  return (mod_mul(a, mminvprime(b, m), m) + m) % m;
}

ll ncr(ll n, ll r, vector<ll> fact, ll m) {
  return mod_mul(mod_mul(fact[n], mminvprime(fact[r], m),m),
                 mminvprime(fact[n - r],m),m);
}

void solve() {
    int k,n;
    cin>> k >> n;
    int d = n-k;
    
    int i=1;
    int j=2;
    cout<<"1"<<" ";
    
    int cnt=1;
    while(cnt<k &&  i<=n && d>0) {
        i=i+j;
        cout<<i<<" ";
        j++;
        d=d-j+1;
        cnt++;
    }
    
    while(i<=n  && cnt<k) {
        i++;
        cout<<i<<" ";
        cnt++;
    }
    cout<<"\n";
}

signed main() {
    ll t = 1;
    cin>>t;
    while(t--) {
      solve();
    }
  
}


Comments

Submit
0 Comments
More Questions

63A - Sinking Ship
1704B - Luke is a Foodie
298B - Sail
239A - Two Bags of Potatoes
1704E - Count Seconds
682A - Alyona and Numbers
44A - Indian Summer
1133C - Balanced Team
1704A - Two 0-1 Sequences
1467A - Wizard of Orz
1714E - Add Modulo 10
1714A - Everyone Loves to Sleep
764A - Taymyr is calling you
1714B - Remove Prefix
1264F - Beautiful Fibonacci Problem
52A - 123-sequence
1543A - Exciting Bets
1714D - Color with Occurrences
215B - Olympic Medal
1445A - Array Rearrangment
1351A - A+B (Trial Problem)
935B - Fafa and the Gates
1291A - Even But Not Even
1269A - Equation
441A - Valera and Antique Items
1702C - Train and Queries
816B - Karen and Coffee
838D - Airplane Arrangements
148B - Escape
847G - University Classes